package divide_and_conquer;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/594wfg/
//实现一个十进制数字报数程序，请按照数字从小到大的顺序返回一个整数数列，该数列从数字 1 开始，到最大的正整数 cnt 位数字结束。
public class LCR_135报数 {
    //暴力
    class Solution {
        public int[] countNumbers(int cnt) {
            int end = (int) (Math.pow(10,cnt) - 1);
            int[] ans = new int[end];
            for(int i=0; i<end; i++){
                ans[i] = i+1;
            }
            return ans;
        }
    }
    //大数打印
    class Solution2 {
        int[] res;
        int nine = 0, count = 0, start, cnt;
        char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
        public int[] countNumbers(int cnt) {
            this.cnt = cnt;
            res = new int[(int)Math.pow(10, cnt) - 1];
            num = new char[cnt];
            start = cnt - 1;
            dfs(0);
            return res;
        }
        void dfs(int x) {
            if(x == cnt) {
                String s = String.valueOf(num).substring(start);
                if(!s.equals("0")) res[count++] = Integer.parseInt(s);
                if(cnt - start == nine) start--;
                return;
            }
            for(char i : loop) {
                if(i == '9') nine++;
                num[x] = i;
                dfs(x + 1);
            }
            nine--;
        }
    }
}
